package com.wang.interview.N03_stair;

import java.util.Scanner;

/**
 * @author: wang
 * @date: 2021/7/13 08:49
 * @description:
 * n步台阶，一次只能走1或者2步，有多少种走法？
 * 使用递归
 */
public class Recursion {
    /**
     *  1     f(1)1 表示全走1步的走法
     *  2     f(2)2 表示全走2步的走法  f(n)表示混合走
     *  3     f(1)1 + f(2)2;    f(3)=3 ; // n每加一，就会让上一次走法还剩下一步不会增加选择，而对于上上次则增加了两步增加了两步台阶所需要的两次
     *  4     f(3)3 + f(2)2;    f(4)=5   //对于此步; 就相当于f(3)多了一步，f(2)多了两步
     *  5     f(4)5 + f(3)3;    f(5)=8   //f(4)多了一步，f(3)多了两步，即n+1，因为每次最大只能走两步，所以除了新增的两步其余的选择数还是和之前的一样
     */

    public static int f(int n){
        if (n<=0){
            throw new IllegalArgumentException(n+"n不能小于等于0");
        }
        if (n==1 || n==2){
            return n;
        }
        return f(n-1)+f(n-2);
    }

    public static void main(String[] args) {
        System.out.print("请输入一个大于0的整数：");
        Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        long i1 = System.currentTimeMillis();
        System.out.println(f(i));
        long i2 = System.currentTimeMillis();
        System.out.println(i2-i1);
        sc.close();
    }
}
